package 二叉树.有序数组转换二叉搜索树;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/6/1 20:25
 * @description:
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        int[] array = {-10,-3,0,5,9};
        System.out.println(sortedArrayToBST(array).val);
    }

    //递归解法 每次选择升序序列的中间元素作为根节点 （基本思想和有序链表转换成二叉搜索树相同）
    public static TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums, 0, nums.length - 1);
    }

    private static TreeNode dfs(int[] nums, int lo, int hi) {
        if (lo > hi) {
            return null;
        }
        // 以升序数组的中间元素作为根节点 root。
        int mid = lo + (hi - lo) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        // 递归的构建 root 的左子树与右子树。
        root.left = dfs(nums, lo, mid - 1);
        root.right = dfs(nums, mid + 1, hi);
        return root;
    }

}
